1. Field of the Invention
The present invention concerns in general terms a method for obtaining from a block turbo-code an error correcting code of desired parameters The invention concerns also a method for decoding such an error correcting code
2. Description of the Related Art
As it is well known, turbo-codes were originally introduced by C Berrou, A. Glavieux and P. Thitimajshima in an article entitled “Near Shannon Limit Error Correcting and Decoding Turbo-codes” published in ICC-1993 Conference Proceedings, pages 1064–1070 Turbo-codes have subsequently been the subject of many developments
Broadly speaking, the turbo-coding principle is based on the concatenation of a plurality of elementary coding steps, each using a simple code, hereinafter referred to as elementary code. The elementary coding steps are separated by interleaving steps modifying the order in which the data is taken into account
Two large classes of turbo-codes are distinguished parallel turbo-codes where the elementary coding steps are carried out in parallel and serial turbo-codes where the elementary coding steps are carried out sequentially. Block turbo-codes (BTCs) are a special class of serial turbo-codes where the elementary codes are block codes like Hamming, RS (Reed Solomon) or BCH (Bose-Chaudhuri-Hocquenghem) codes
FIG. 1 illustrates schematically the structure of a block turbo-coder The block turbo-coder 100 comprises elementary block coders 1101, 110P concatenated in series, where P is called the dimension of the turbo-code. The turbo-coder operates on data block of P dimensions, each elementary coder operating on one dimension only. Without loss of generality, it will be assumed in the following that P=2.
A block of data represented by a matrix of k1×k2 symbols is input to a first block coder 1101. It should be noted that, depending on the type of block code, the symbols may be bits or words The first block coder 1101 operates on the rows (or the columns) of the matrix and appends to the original data (also called the systematic information or the systematic part) a first redundance information (or redundancy part, here represented by a dotted area) to form a matrix of size n1×k2. The second block coder 1102 operates on the columns (or the rows) of the n1×k2 matrix and appends thereto a second redundancy information (dotted area) to form a matrix of size n1×n2 The systematic part is represented by the blank area of size k1×k2 
In general, an error correcting code is denoted (N,K,D) where N is the size of the code, K is the size of the original information (ie the size of the systematic information in case of a systematic code) and D is the minimum Hamming distance of the code If (n1, k1, d1) and (n2, k2, d2) are respectively the block codes used by the first and the second block coders, the resulting turbo-code is in fact a product code of minimum Hamming distance d=d1×d2 and therefore denoted (n1×n2, k1×k2, d1×d2). Hence, by concatenating block codes of small Hamming distances a block turbo-code can be obtained with a much larger Hamming distance
The coded data output by the block turbo-coder is M-ary or binary modulated (eg BPSK modulated) prior to being transmitted over a transmission channel At the receiving side, a demodulator outputs soft values reflecting the probabilities of transmitted M-ary symbols or bits. These soft values can be labelled in terms of probabilities, likelihood ratios or, more commonly, in terms of log likelihood ratios (LLRs)
FIG. 2 illustrates schematically the structure of a block turbo-decoder The information is presented as a P-dimensional block of soft values supplied by the demodulator. The turbo-decoding process involves a series of iterations l, ,k, upon the input block, each iteration consisting in a concatenation of elementary decoding steps, each elementary decoding step operating on one dimension of the input block. For example, (1) in FIG. 2 represents the concatenation of elementary decoding steps (or elementary decoders) 210l(l), . . . ,210p(l)) of the first iteration and (k) represents the concatenation of the elementary decoding steps (or elementary decoders) 201l(k), . . . ,210p(k) of the last iteration The last iteration is followed by a hard decision 220, eg a thresholding, for obtaining the decoded bits or words
The input information of an elementary decoder is so called a priori information and consists of a noisy version of the output of the corresponding elementary coder. From this information and the coding law of the corresponding elementary coder, the elementary decoder generates an a posteriori information, which is an estimation of higher reliability of the information input to the corresponding elementary coder The additional information provided by the a posteriori information with respect to the a priori information is referred to as extrinsic information
Various algorithms can be used in the elementary decoders 210l(j), for example the Chase algorithm disclosed in the article (entitled “Near optimum product codes” published in Proc IEEE Globecom of 1994, pages 339–343, or the algorithm described in the article of J Lodge et al. entitled “Separate MAP filters for the decoding of product of concatenated codes” published in Proc ICC'93, pages 1740–1745.
Each elementary decoder receives the entirety of the input block and carries out an estimation of the soft values of the said block, according to the coding dimension of the corresponding elementary coder, by using for example the Chase algorithm mentioned above If the soft values are expressed in terms of LLRs, the a posteriori information output by the decoder is subtracted from the a priori information to obtain a block of extrinsic information having the same size as the input block. The extrinsic information is then added to the input block to serve as a priori information for the next elementary decoder. It should be noted that the order of the elementary decoders/decoding steps is of a little importance, each operating on one or hogonal dimension of the n-dimensional block. By successive passes from one dimension to another and from one iteration to the next one, the estimation of the systematic information gains reliability
More specifically, the structure of an elementary decoder decoding the pth dimension is represented in FIG 3. The input block is represented by a matrix R of soft values supplied by the demodulator, assumed to be expressed here in terms of LLRs The elementary decoder inputs a matrix of extrinsic values Wp and outputs a matrix of extrinsic values Wp+1, the matrix of extrinsic values input by the first decoder at the first iteration being W1=0 The extrinsic values are then weighted in 310 by a weighting factor αp before being added to the soft values of the matrix R The purpose of the weighting factor αp is to reduce the contribution of the extrinsic information, the reliability of which is low during the first iterations The resulting matrix Rp of soft values can therefore be writtenRp=R+αpWp  (1)The soft values are decoded in 330 eg by using the Chase algorithm, thus providing an a posteriori information of higher reliability represented by a matrix R′p of soft values A new matrix of extrinsic values is obtained by subtracting in 340 the a priori information to the a posteriori information, that is.Wp+1=R′p−Rp  (2)
At the last iteration, the systematic part of R′p is thresholded in the hard decision unit 2
An important characteristic of an error correcting code of parameters (N,K,D) is the ratio R=K/N, called the code rate, which gives the coding efficiency of the code The parameters of a product code of elementary codes (np,kp,dp), denoted       ∏          p      =      1        P    ⁢          ⁢      (                  n        p            ,              k        p            ,              d        p              )  are given by.                                           N            =                                          ∏                                  p                  =                  1                                P                            ⁢                                                          ⁢                              n                p                                              ;                      K            =                                          ∏                                  p                  =                  1                                P                            ⁢                                                          ⁢                              k                p                                                    ,                  D          =                                    ∏                              p                =                1                            P                        ⁢                                                  ⁢                          d              p                                                          (        3        )            and therefore   R  =            ∏              p        -        1            P        ⁢                  ⁢          r      p      where rp−kp/np is the code rate of the pth elementary code
Another important characteristic of an error correcting code is the so called asymptotic gain of the code, defined as the ratio, expressed in decibels, of the energies per information bit Eb which are necessary, without coding and with coding, respectively, for achieving a given binary error rate (BER) The asymptotic gain G of a product code is equal to the sum of the asymptotic gains of the elementary codes                     G        =                              ∑                          p              =              1                        P                    ⁢                      G            p                                              (        4        )            
In practice, for a given telecommunication system, the values of the parameters K′ and N′ of an error correcting code are often imposed On the other hand, the parameters np and kp of the known block codes (np,kp,dp) cannot take but few possible values It follows (3) that a block turbo-code offers a very limited choice in terms of available parameters K and N Furthermore, it is often found necessary to adapt the error correcting code parameters to the condition of the transmission channel. For example, if the quality of the transmission channel is good, a code of high rate can be chosen whereas if the quality of the transmission channel is poor, a code of low rate is required. In order to broaden the choice of values for the parameters K and N of a block turbo-code, the general techniques of code shortening, code puncturing can be applied
The shortening of a block code (n,k,d) consists in setting to zero a plurality s of bits (called shortened bits) of the information to be coded Although these zero values are taken into account for generating the redundancy part, they are not transmitted to the receiver. The k−s remaining bits of the systematic information and the n−k bits of the redundancy information define a shortened code (n−s,k−s,d) where d≧d. At the receiving side, the decoder knows the positions and values (equal to 0) of the shortened bits and therefore they can be given the highest level of reliability (i.e. −1 if LLRs are used). The a priori knowledge of the s shortened bits improves the decoding of the n−s remaining bits. Shortened block codes can be concatenated to form a shortened block turbo code denoted       ∏          p      =      1        P    ⁢          ⁢      (                            n          p                -                  s          p                    ,                        k          p                -                  s          p                    ,              d        p        s              )  Typically, the shortened bits are arranged along rows and columns to simplify the decoding process. FIG. 4 shows an example of such a bidimensional shortened block turbo code. The shortened bits set to zero have been illustrated by the areas filled in grey The parameters of the illustrated shortened code are ((n1−s1)×(n2−s2),(k1−s1)×(k2−s2),(d1×d2) and hence the rate of the shortened code is lower than the rate of the original code.                               R          1                =                                                            (                                                      k                    1                                    -                                      s                    1                                                  )                            ⁢                              (                                                      k                    2                                    -                                      s                    2                                                  )                                                                    (                                                      n                    1                                    -                                      s                    1                                                  )                            ⁢                              (                                                      n                    2                                    -                                      s                    2                                                  )                                              <          R                                    (        5        )            
The puncturing of a code consists in omitting to transmit certain bits of the code, most often belonging to the redundancy part if the code is systematic. At the receiving side, the punctured bits are attributed any value and the lowest reliability level (0 if LLRs are used).
FIG. 5 shows a punctured bidimensional block turbo code. The punctured bits are represented by squares filled in black. If x is the total number of punctured bits, the parameters of the punctured code are (n1n2,k1k2−x,d) with d<d and the rate of the punctured code is higher than rate of the original code                               R          1                =                                                            k                1                            ⁢                              k                2                                                                                      n                  1                                ⁢                                  n                  2                                            -              x                                >          R                                    (        6        )            
Since the number of parity bits is lower and since the punctured bits have the lowest reliability level, the gain of the punctured code is lower than the gain of the original code
The combination of shortening and puncturing significantly extends the choice of achievable parameters In particular, for a shortened and punctured bidimensional block turbo-code, the parameters are ((n1−s1)×(n2−s2)−x,(k1−s1)×k2−s2), d1s×d2s) and therefore the code rate can be written.                               R          sp                =                                            (                                                k                  1                                -                                  s                  1                                            )                        ⁢                          (                                                k                  2                                -                                  s                  2                                            )                                                                          (                                                      n                    1                                    -                                      s                    1                                                  )                            ⁢                              (                                                      n                    2                                    -                                      s                    2                                                  )                                      -            x                                              (        7        )            
By carefully choosing the parameters of the elementary block codes, the shortening lengths and the amount of punctured bits, the desired parameters N,K can be obtained These codes are called parametric block turbo-codes.
However, the larger choice of parameters is balanced by the lower asymptotic gains of the codes obtained, basically due to puncturing.
It has been proposed in the prior art, e.g in EP-A-827285, to distribute uniformly the shortened bits along the different dimensions of the turbo-code and next to the punctured bits. Such a turbo-code is illustrated in FIG. 6 where the punctured bits are represented in black and the shortened bits in grey. By so doing, the high reliability of the shortened bits compensates for the low reliability of the punctured bits and consequently improves the asymptotic gain value of the shortened punctured turbo-code However, the puncturing necessary implies at waste of redundancy and therefore a sub-optimal asymptotic gain